1. Field of the Invention
The present invention relates generally to the encoding of digital data and, more specifically, to MATCH and MATCH.sub.-- ADDRESS signal prioritization in a content addressable memory encoder for a system in which more than one match is a possible search routine result.
2. Description of Related Art
Random access memory ("RAM") is perhaps the most common form of integrated circuit memory available in the state of the art. However, RAM devices are not suited for use in systems which process associative data. For example, the well known methodology of sequentially accessing data when addressing the RAM is inefficient for systems involving stored information involving pattern recognition, data compression, natural language recognition, sparse matrix processes, and data-base interrogation. The address associated with the desired stored data may not be known. For this type of data, it is more efficient to interrogate a memory by supplying a compressed subset of the desired data or a code representative of the full data set. The memory responds by indicating either absence of the desired data set or presence of the data set by issuing a match signal and an associated address in the memory bank for the data set.
In the 1980's, another type of memory device was developed to have ambiguous and non-contiguous addressing and was dubbed the content addressable memory ("CAM"). See e.g., U.S. Pat. No. 3,701,980 (Mundy). In essence, for this type of associative data search, the entire CAM can be searched in a single clock cycle, giving it a great advantage over the sequential search technique required when using a RAM device.
As an example, a string dictionary can be stored in a CAM and used in generating Lev-Zempel compressed output data (hereinafter "LZ"; generically used for any LZ data compression technique; see "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Transactions on Information Theory, 24(5):530-536, September 1978, incorporated herein by reference). The input data signal to the CAM would comprise a bit string representation of the data which is being searched for in the CAM. The output would be a signal indicative as to whether the data was found, the MATCH signal, and, if found, the location within the CAM, the MATCH.sub.-- ADDRESS. Obtaining this MATCH and MATCH.sub.-- ADDRESS information is done with what is called in the art a "match encoder." As another example, for color hard copy printing a data base may be stored in a CAM where the data consists of bit strings comprising tristimulus space values--cyan, yellow, magenta ("CYM"). U.S. Pat. No. 5,455,576 by Clark II et al. teaches an Apparatus and Methods for Lempel Ziv Data Compression with Improved Management of Multiple Dictionaries in Content Addressable Memory, incorporated herein by reference.
The problem with CAM devices is that compared to RAM each individual cell structure is relatively complex. See e.g., U.S. Pat. No. 4,780,845 (Threewitt). Thus, for the same integrated circuit real estate, a CAM device can not match the density, speed, or low-power performance of a RAM device. Integrated circuit process improvements generally affect both types of devices equally, so that in relative terms, CAM architects can not do much to narrow the performance gap.
Perhaps the most critical path through the CAM is the search cycle; that is, the time from receipt of an input data signal, or code, to the encoder input to determine if the CAM has the desired data set to the time of the output of a match or mismatch indication, and, if a MATCH signal is generated, the MATCH.sub.-- ADDRESS. Depending on the nature of the data, the CAM core memory can contain locations with redundant information; see e.g., U.S. Pat. No. 5,455,576, supra. Therefore, a search will result in a MATCH for more than one MATCH.sub.-- ADDRESS. When such is the case, there is a need to determine which MATCH.sub.-- ADDRESS is to be selected, referred to herein as "prioritization."